#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <string.h>

#define __USE_MISC
#include <sys/mman.h>


// cube - side - element

// number of sides in cube
int const kSideNum = 6;
// each side contains this number of elements
int const kElemNum = 4;
// number of colors
int const kColorNum = 6;
// number of elements in cube
int const kTotalElemNum = 24;
int const kHashTableSize = (1 << 25);
typedef enum {
    RED,
    GREEN,
    YELLOW,
    PURPLE,
    BLUE,
    DARK
} Colors;

typedef uint8_t Cube[24];
typedef uint64_t Hash;

void validateCube(Cube cube) {
    assert(cube[0] == RED);
    assert(cube[15] == GREEN);
    assert(cube[21] == YELLOW);
    for (int i = 0; i < kTotalElemNum; i++) {
        assert(cube[i] < kColorNum);
    }
}

// Given a character [R,G,Y,P,B,D] returns the Color (number from 0 to 5)
int parseChar (char ch) {
    switch (ch) {
        case 'R' : return RED;
        case 'G' : return GREEN; 
        case 'Y' : return YELLOW; 
        case 'P' : return PURPLE; 
        case 'B' : return BLUE;
        case 'D' : return DARK;
        default : assert(0);
    }
}

// parses input string into cube representation
void stringToCube (char *str, Cube cube) {
    //printf ("%s\n", str);
    int len = strlen(str);
    assert (len == 29);
    for (int i = 0; i < kSideNum; i++) {
        for (int j = 0; j < kElemNum; j++) {
            //printf("cube = %d ", j + i * kElemNum);
            //printf("str = %d ", j + i * (kElemNum + 1));
            cube[j + i * kElemNum] = parseChar(str[j + i*(kElemNum + 1)]);
        }
        //printf("\n");
    }
    validateCube(cube);
}

void cubeToString(Cube cube, char* str) {
    validateCube(cube);
    int ind = 0;
    for (int i = 0; i < kSideNum; i++) {
        for (int j = 0; j < kElemNum; j++) {
            //printf("%d\n", ind);
            switch (cube[j + i * kElemNum]) {
                case RED    : str[ind] = 'R'; break;
                case GREEN  : str[ind] = 'G'; break;
                case YELLOW : str[ind] = 'Y'; break;
                case BLUE   : str[ind] = 'B'; break;
                case PURPLE : str[ind] = 'P'; break;
                case DARK   : str[ind] = 'D'; break;
                default: assert(0);
            }
            ind++;
        } 
        //printf("%d\n", ind);
        str[ind] = '-';
        ind++;
    }
    assert(ind == 30);
    //printf("%d\n", ind);
    str[ind - 1] = '\0';
    //printf("%s\n", str);
}

void printCube(Cube cube) {
    for (int i = 0; i < kTotalElemNum; i++)
        printf("%d ", cube[i]);
    printf("\n");
}

Hash cubeToHash(Cube cube) {
    // validateCube(cube);
    Hash hash = 0;
    for (int i = 1; i < kTotalElemNum - 1; i++) {
        hash = (hash + cube[i]) * kColorNum;
    } 
    hash += cube[kTotalElemNum - 1];
    assert(hash < 789730223053602816ULL);
    //printf("%llu\n", hash);
    return hash;
}

void hashToCube(Hash hash, Cube cube) {
    assert(hash < 789730223053602816ULL);
    Hash t = hash;
    for (int i = kTotalElemNum - 1; i > 1; i--) {
        int rem = t % kColorNum;
        cube[i] = rem;
        t = (t - rem) / kColorNum;
    } 
    assert(t < kColorNum);
    cube[1] = t;
    cube[0] = 0;
    // validateCube(cube);
    //printf("h1 %llu\n", hash);
    //printf("h2 %llu\n", cubeToHash(cube));
    assert(hash == cubeToHash(cube));
}

Hash addDepth(Hash hash, uint64_t depth) {
    assert(depth < 16);
    assert(hash < (1ULL << 60));
    depth = (depth << 60);
    return hash + depth;
}

Hash removeDepth(Hash hash) {
    return ((hash << 4) >> 4);
}

uint64_t getDepth(Hash hash) {
    return (hash >> 60);
}

static const Hash *hashTable = (Hash*)0x200000000;

static int insert_count, n_collisions;

void initHashTable() {
    void *res = mmap((void*)hashTable, kHashTableSize * sizeof(Hash), 
            PROT_READ|PROT_WRITE,
            MAP_PRIVATE | MAP_ANON | MAP_FIXED,
            -1, 0);
    assert(res == (void*)hashTable);
    fprintf(stderr, "inited %lx\n", hashTable[0]);
}

void clearHashTable() {
    insert_count = 0;
    n_collisions++;
    memset((void*)hashTable, 0, kHashTableSize * sizeof(Hash));
}

int insertIntoHashTable(Hash hash, uint16_t depth) {
    assert(removeDepth(hash) == hash);
    for (int i = 0; i < 64; i++) {
        if (i) n_collisions++;
        int ind = (hash + i) % kHashTableSize;
        Hash hash1 = hashTable[ind];
        if (!hash1) {
            ((Hash*)hashTable)[ind] = addDepth(hash, depth);
            insert_count++;
            return 1;
        }
        if (removeDepth(hash1) == hash) {
            return 0;
        }
    }
    assert(0);
    return 0;
}



void rotateRight(Cube cube, Cube new_cub) {
    new_cub[0] = cube[0];
    new_cub[1] = cube[1];
    new_cub[2] = cube[22];
    new_cub[3] = cube[23];
    new_cub[4] = cube[7];
    new_cub[5] = cube[4];
    new_cub[6] = cube[5];
    new_cub[7] = cube[6];
    new_cub[8] = cube[18];
    new_cub[9] = cube[19];
    new_cub[10] = cube[10];
    new_cub[11] = cube[11];
    new_cub[12] = cube[12];
    new_cub[13] = cube[13];
    new_cub[14] = cube[14];
    new_cub[15] = cube[15];
    new_cub[16] = cube[16];
    new_cub[17] = cube[17];
    new_cub[18] = cube[2];
    new_cub[19] = cube[3];
    new_cub[20] = cube[20];
    new_cub[21] = cube[21];
    new_cub[22] = cube[8];
    new_cub[23] = cube[9];
}

void rotateTop(Cube cube, Cube new_cub) {
    new_cub[0] = cube[0];
    new_cub[1] = cube[5];
    new_cub[2] = cube[6];
    new_cub[3] = cube[3];
    new_cub[4] = cube[4];
    new_cub[5] = cube[9];
    new_cub[6] = cube[10];
    new_cub[7] = cube[7];
    new_cub[8] = cube[8];
    new_cub[9] = cube[13];
    new_cub[10] = cube[14];
    new_cub[11] = cube[11];
    new_cub[12] = cube[12];
    new_cub[13] = cube[1];
    new_cub[14] = cube[2];
    new_cub[15] = cube[15];
    new_cub[16] = cube[19];
    new_cub[17] = cube[16];
    new_cub[18] = cube[17];
    new_cub[19] = cube[18];
    new_cub[20] = cube[20];
    new_cub[21] = cube[21];
    new_cub[22] = cube[22];
    new_cub[23] = cube[23];
}

void rotateBack(Cube cube, Cube new_cub) {
    new_cub[0] = cube[0];
    new_cub[1] = cube[1];
    new_cub[2] = cube[2];
    new_cub[3] = cube[3];
    new_cub[4] = cube[4];
    new_cub[5] = cube[5];
    new_cub[6] = cube[23];
    new_cub[7] = cube[20];
    new_cub[8] = cube[11];
    new_cub[9] = cube[8];
    new_cub[10] = cube[9];
    new_cub[11] = cube[10];
    new_cub[12] = cube[17];
    new_cub[13] = cube[18];
    new_cub[14] = cube[14];
    new_cub[15] = cube[15];
    new_cub[16] = cube[16];
    new_cub[17] = cube[6];
    new_cub[18] = cube[7];
    new_cub[19] = cube[19];
    new_cub[20] = cube[13];
    new_cub[21] = cube[21];
    new_cub[22] = cube[22];
    new_cub[23] = cube[12];
}

void genMoves(Cube cube, Cube arr_cube[9]) {
    Cube t;
    //right
    rotateRight(cube, arr_cube[0]);
    rotateRight(arr_cube[0], arr_cube[1]);
    rotateRight(arr_cube[1], arr_cube[2]);
    rotateRight(arr_cube[2], t);
    assert(memcmp(cube, t, sizeof(t)) == 0);
    //top
    rotateTop(cube, arr_cube[3]);
    rotateTop(arr_cube[3], arr_cube[4]);
    rotateTop(arr_cube[4], arr_cube[5]);
    rotateTop(arr_cube[5], t);
    assert(memcmp(cube, t, sizeof(t)) == 0);
    // back
    rotateBack(cube, arr_cube[6]);
    rotateBack(arr_cube[6], arr_cube[7]);
    rotateBack(arr_cube[7], arr_cube[8]);
    rotateBack(arr_cube[8], t);
    assert(memcmp(cube, t, sizeof(t)) == 0);
}

char* moveToString(uint16_t move) {
    switch (move) {
        case 0: return "Right 1";
        case 1: return "Right 2";
        case 2: return "Right 3";
        case 3: return "Top 1";
        case 4: return "Top 2";
        case 5: return "Top 3";
        case 6: return "Back 1";
        case 7: return "Back 2";
        case 8: return "Back 3";
        default: assert(0);                
    }
}

void printMoves(uint16_t moves_stack[], int d) {
    for (int i = d; i > 0; i--) {
        printf("%s\n", moveToString(moves_stack[i]));
    }
}

int BFS(Cube c0, Hash target, uint16_t max_depth) {
    // printf("zz1\n"); fflush(stdout);
    clearHashTable();
    insertIntoHashTable(cubeToHash(c0), 0);
    // printf("zz1\n"); fflush(stdout);
    for (uint16_t depth = 1; depth < max_depth; depth++) {
        // printf("BFS: depth = %d\n", depth);
        for (size_t i = 0; i < kHashTableSize; i++) {
            Hash h = hashTable[i];
            if (!h || getDepth(h) != depth - 1) continue;
            // printf("d %d %d: %lx\n", depth, (int)getDepth(h), h);
            if (target == removeDepth(h)) {
                printf("found target\n");
            }
            Cube c;
            hashToCube(removeDepth(h), c);
            Cube moves[9];
            genMoves(c, moves);
            for (int m = 0; m < 9; m++) {
                int ins = insertIntoHashTable(cubeToHash(moves[m]), depth);
                // printf("insert: %d %lx\n", ins, cubeToHash(moves[m]));
            }
        }
        printf("depth: %d: %d collisions %d\n", depth, insert_count, n_collisions);
    }
}


void test(char *str){
    Cube cube;
    char str_cmp[30];
    stringToCube (str, cube);
    cubeToString(cube, str_cmp);
    assert (strcmp(str, str_cmp) == 0);
    Cube cube_cmp;
    Hash hash = cubeToHash(cube);
    //printf("h3 %llu\n", hash);
    hashToCube(hash, cube_cmp);
    //printCube(cube);
    //printCube(cube_cmp);
    cubeToString(cube_cmp, str_cmp);
    assert (strcmp(str, str_cmp) == 0);
    //-----------
    Cube moves[9];
    genMoves(cube, moves);
    cubeToString(moves[0], str_cmp);
    assert(strcmp(str_cmp, "RRYY-BBBB-DDPP-GGGG-DDRR-YYPP") == 0);
    cubeToString(moves[1], str_cmp);
    assert(strcmp(str_cmp, "RRPP-BBBB-RRPP-GGGG-DDYY-YYDD") == 0);
    cubeToString(moves[2], str_cmp);
    assert(strcmp(str_cmp, "RRDD-BBBB-YYPP-GGGG-DDPP-YYRR") == 0);

    cubeToString(moves[3], str_cmp);
    assert(strcmp(str_cmp, "RBBR-BPPB-PGGP-GRRG-DDDD-YYYY") == 0);
    cubeToString(moves[4], str_cmp);
    assert(strcmp(str_cmp, "RPPR-BGGB-PRRP-GBBG-DDDD-YYYY") == 0);
    cubeToString(moves[5], str_cmp);
    assert(strcmp(str_cmp, "RGGR-BRRB-PBBP-GPPG-DDDD-YYYY") == 0);
    
    cubeToString(moves[6], str_cmp);
    assert(strcmp(str_cmp, "RRRR-BBYY-PPPP-DDGG-DBBD-GYYG") == 0);
    cubeToString(moves[7], str_cmp);
    assert(strcmp(str_cmp, "RRRR-BBGG-PPPP-BBGG-DYYD-DYYD") == 0);
    cubeToString(moves[8], str_cmp);
    assert(strcmp(str_cmp, "RRRR-BBDD-PPPP-YYGG-DGGD-BYYB") == 0);
}



int main (int argc, char** argv) {
    initHashTable();
    //Cube cube;
    // test("RRRR-BBBB-PPPP-GGGG-DDDD-YYYY");
    Cube target_cube;
    stringToCube("RRRR-BBBB-PPPP-GGGG-DDDD-YYYY", target_cube);
    Hash target_hash = cubeToHash(target_cube);
    Cube cube;
    if (argc == 2) {
        char* str = argv[1];
        if (strlen(str) != 29) {
            printf ("Incorrect input\n");
            return 0;
        }
        stringToCube(str, cube);
        BFS(cube, target_hash, 13);
        //int res1 = search(cube, target_hash);
        //int res2 = search(target_cube, cubeToHash(cube));
       // assert(res1 == res2);
    } else {
        BFS(target_cube, 0, 13);
    }
    return 0;
}

// RRYY-PPPP-DDDD-RRBG-YBBB-GYGG
